#include "sort.h"

// 交换位置
void swap(int* arr, int i, int j)
{
    int t = arr[i];
    arr[i] = arr[j];
    arr[j] = t;
}

void selection_sort(int* a, int len) 
{

    int i,j,temp;
 
    for (i = 0 ; i < len - 1 ; i++) {
        int min = i;                 
        for (j = i + 1; j < len; j++)     
        {
            if (a[j] < a[min]) {
                min = j;    
            }
        }
        if(min != i)
        {
            temp=a[min];  
            a[min]=a[i];
            a[i]=temp;
        }
    }
}


void shell_sort(int arr[], int len) {
    int gap, i, j;
    int temp = 0;
    for (gap = len >> 1; gap > 0; gap = gap >> 1)
        for (i = gap; i < len; i++) {
            temp = arr[i];
            for (j = i - gap; j >= 0 && arr[j] > temp; j -= gap)
                arr[j + gap] = arr[j];
            arr[j + gap] = temp;
        }
}




// 两个子数组合并 
// 子数组一 arr[l..m]
// 子数组二 arr[m+1..r]
void merge(int arr[], int l, int m, int r)
{
	int i, j, k;
	int n1 = m - l + 1;
	int n2 = r - m;
	int L[n1], R[n2];
	for (i = 0; i < n1; i++)
		L[i] = arr[l + i];
	for (j = 0; j < n2; j++)
		R[j] = arr[m + 1 + j];

	/* 将临时数组合并回arr[l..r]*/
	i = 0; // 第一个子数组的初始索引
	j = 0; // 第二个子数组的初始索引
	k = l; // 合并子数组的初始索引
	while (i < n1 && j < n2) {
		if (L[i] <= R[j]) {
			arr[k] = L[i];
			i++;
		}
		else {
			arr[k] = R[j];
			j++;
		}
		k++;
	}
	while (i < n1) {
		arr[k] = L[i];
		i++;
		k++;
	}
	while (j < n2) {
		arr[k] = R[j];
		j++;
		k++;
	}
}

void mergeSort(int arr[], int l, int r)
{
	if (l < r) {
		int m = l + (r - l) / 2;
		mergeSort(arr, l, m);
		mergeSort(arr, m + 1, r);
		merge(arr, l, m, r);
	}
}



void quicksort(int* arr, int start, int end)
{
    int pivot, index;
    if (end <= 1)
        return;
    pivot = arr[start + end / 2];
    swap(arr, start, start + end / 2);
    index = start;
    for (int i = start + 1; i < start + end; i++) {
        if (arr[i] < pivot) {
            index++;
            swap(arr, i, index);
        }
    }
    swap(arr, start, index);
    quicksort(arr, start, index - start);
    quicksort(arr, index + 1, start + end - index - 1);
}

int shellSort1(int arr[], int n)
{
    for (int gap = n/2; gap > 0; gap /= 2)
    {
        for (int i = gap; i < n; i += 1)
        {
            int temp = arr[i];
            int j;           
            for (j = i; j >= gap && arr[j - gap] > temp; j -= gap)
                arr[j] = arr[j - gap];
            arr[j] = temp;
        }
    }
    return 0;
}

// 获取数组中的最大数
int getMax(int arr[], int n)
{
	int mx = arr[0];
	for (int i = 1; i < n; i++)
		if (arr[i] > mx)
			mx = arr[i];
	return mx;
}


void countSort(int arr[], int n, int exp)
{
	int output[n]; 
	int i, count[10] = { 0 };
	for (i = 0; i < n; i++)
		count[(arr[i] / exp) % 10]++;
	for (i = 1; i < 10; i++)
		count[i] += count[i - 1];
	for (i = n - 1; i >= 0; i--) {
		output[count[(arr[i] / exp) % 10] - 1] = arr[i];
		count[(arr[i] / exp) % 10]--;
	}
	for (i = 0; i < n; i++)
		arr[i] = output[i];
}

void radixsort(int arr[], int n)
{
	int m = getMax(arr, n);
	for (int exp = 1; m / exp > 0; exp *= 10)
		countSort(arr, n, exp);
}




